<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      var getModifiedArray = function (length, updates) {
        // 方法一：暴力法（）---时间：O（n^2）（）---空间：O（1）（）
        // const arr = new Array(length).fill(0);
        // for (let i = 0; i < updates.length; i++) {
        //   const start = updates[i][0];
        //   const end = updates[i][1];
        //   const val = updates[i][2];
        //   for (let j = start; j <= end; j++) {
        //     arr[j] += val;
        //   }
        // }
        // return arr;

        // 方法一：差分数组（）---时间：O（）（）---空间：O（）（）
        const diff = new Array(length).fill(0);
        const res = new Array(length).fill(0);
        function add(start, end, value) {
          diff[start] += value;
          if(end + 1 < length){
            diff[end + 1] -= value;
          }
        }
        for (let i = 0; i < updates.length; i++) {
          add(updates[i][0], updates[i][1], updates[i][2]);
        }
        res[0] = diff[0];
        for (let i = 1; i < diff.length; i++) {
          res[i] = res[i - 1] + diff[i];
        }
        return res;
      };
      console.log(
        getModifiedArray(5, [
          [1, 3, 2],
          [2, 4, 3],
          [0, 2, -2],
        ])
      );
      // 原始
      // [8,5,9,6,1]
      // 差分数组
      // [8,-3,4,-3,-5]
      // [1,3]区间加3
      // this.diff[i] += val
      // [8,0,4,-3,-5]
      // if (j + 1 < this.diff.length) {
      //    this.diff[j + 1] -= val;
      // }
      // [8,0,4,-3,-8]
      // res[i] = res[i - 1] + this.diff[i];
      // [8,8,12,9,1]
      // 这里的原数组 nums 对应的就是前缀和数组 prefixSum，差分数组 diff 对应的就是前缀和中的原数组 nums。
      // 因此对于假前缀和数组第 [i,j] 位的加减操作，
      // 就可以理解为对原数组第 i 位加减某个数，第 j+1 位进行相反操作，
      // 就可以使前缀和数组表现为第 [i, j] 位同时加减某个数
      // 后两句的解释：
      // 因为对于前缀和数组来说，res[i] 表示的是 res[i-1] 与 nums[i] 的和，
      // res[i+1]=res[i]+nums[i+1]，如果nums[i+1]+3，那res[i+1]就等于res[i]+3+nums[i+1]，会一直累加上去
    </script>
  </body>
</html>
